// 基础二分查找  有序数组中，无重复数据

function baseSearch(arr, val) {
    var low = 0;
    var high = arr.length - 1

    while(low <= high) {
        var mid = Math.floor((low + high) / 2)
        if (arr[mid] == val) {
            return mid
        } else if (arr[mid] > val) {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return -1
}

var arr = [1, 2, 4, 5, 6, 8, 10, 11]
console.log(arr)
console.log('二分查找元素4的下标：', baseSearch(arr, 4))


// 查找第一个值等于给定值的元素下标   易懂
function oneSearch(arr, val) {
    var low = 0;
    var high = arr.length - 1

    while(low <= high) {
        var mid = Math.floor((low + high) / 2)
        if (arr[mid] == val) {
            if (mid == 0 || arr[mid - 1] < val) {
                return mid
            } else {
                high = mid - 1
            }
        } else if (arr[mid] > val) {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return -1

}

// 简化 但不好理解
function oneSearch2(arr, val) {
    var low = 0;
    var high = arr.length - 1

    while(low <= high) {
        var mid = Math.floor((low + high) / 2)
        if (arr[mid] >= val) {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    if (low < arr.length && arr[low] == val) {
        return low
    } else {
        return -1
    }

}


var arr = [1, 2, 4, 4, 4, 4, 5, 6, 8, 10, 12]
console.log(arr)
console.log('二分查找第一个元素4的下标：', oneSearch(arr, 4))

// 查找第一个大于等于给定值的元素
function oneLagSearch(arr, val) {
    var low = 0;
    var high = arr.length - 1

    while(low <= high) {
        var mid = Math.floor((low + high) / 2)
        if (arr[mid] >= val) {
            if (mid == 0 ||arr[mid - 1] < val) {
                return mid
            } else {
                high = mid - 1
            }
        } else {
            low = mid + 1
        }
    }
    return -1

}

var arr = [1, 2, 2, 4, 4, 4, 4, 5, 6, 8, 10, 12, 12, 12]
console.log(arr)
console.log('二分查找第一个大于等于4的下标：', oneLagSearch(arr, 4))